//
//  并查集2.swift
//  Swift-LeetCode
//
//  Created by 卢悦明 on 2024/3/2.
//

import UIKit

/// 第二种并查集实现
class UnionFind_QU: UnionFind {
    /// 查找v的根节点
    /// - Parameter v:
    /// - Returns: 结果
    override func find(_ v: Int) -> Int {
        var v = v
        while v != parents[v] {
            v = parents[v]
        }
        return v
    }
    
    /// 合并v1和v2(v1的根节点嫁接到v2的根节点)
    /// - Parameters:
    ///   - v1: 1
    ///   - v2: 2
    override func union(_ v1: Int, _ v2: Int) {
        let p1 = find(v1)
        let p2 = find(v2)
        if p1 == p2 {
            return
        }
        parents[v1] = p2
    }
}
